package main

import "fmt"

// two questions
// 1. check if matrix is valid magic matrix
// 2. find the largest magic matrix

func validMagic(matrix [][]int, x, y, size int) bool {
	diag1, diag2 := 0, 0
	for i := 0; i < size; i++ {
		diag1 += matrix[x+i][y+i]
	}
	for i := 0; i < size; i++ {
		diag2 += matrix[x+i][y+size-1-i]
	}
	if diag1 != diag2 {
		return false
	}
	for i := 0; i < size; i++ {
		rowSum, colSum := 0, 0
		for j := 0; j < size; j++ {
			// fmt.Printf("%v , %v\n", i, j)
			rowSum += matrix[x+i][y+j]
			colSum += matrix[x+j][y+i]
		}
		if rowSum != diag1 || colSum != diag1 {
			return false
		}
	}
	return true
}

func maxMagic(matrix [][]int) int {
	res := -1
	N, M := len(matrix), len(matrix[0])
	size := 2
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			for i+size <= N && j+size <= M {
				// fmt.Printf("%v , %v, %v\n", i, j, size)
				if validMagic(matrix, i, j, size) == true && size > res {
					res = size
				}
				size++
			}
			size = 2
		}
	}
	return res

}

func main() {
	// input1 := [][]int{
	// 	[]int{7, 3, 8},
	// 	[]int{7, 6, 5},
	// 	[]int{4, 9, 5},
	// }
	input2 := [][]int{
		[]int{4, 3, 4, 5, 3},
		[]int{2, 7, 3, 8, 4},
		[]int{1, 7, 6, 5, 2},
		[]int{8, 4, 9, 5, 5},
	}
	// input3 := [][]int{
	// 	[]int{2, 2, 1, 1},
	// 	[]int{2, 2, 2, 2},
	// 	[]int{1, 2, 2, 2},
	// }
	// fmt.Println(validMagic(input3, 1, 1, 2))
	fmt.Println(maxMagic(input2))
	// fmt.Println(maxMagic(input3))
}
